/*
 * Alloy Analyzer
 * Copyright (c) 2002 Massachusetts Institute of Technology
 *
 * The Alloy Analyzer is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * The Alloy Analyzer is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with the Alloy Analyzer; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package alloy.util;

import java.math.BigInteger;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * {@link Iterator} that yields all possible permutations of
 * n numbers in the range 0,...,n-1.  Static methods let you
 * rank and unrank permutations.  Each of the n! permutations
 * is assigned a unique rank (number) between 0 and n!-1.
 * Unranking means going from rank to the permutation; ranking
 * means going from the permutation to the rank.
 * <p>
 * @see http://www.csr.uvic.ca/~fruskey/Publications/RankPerm.html
 */
public class PermIter implements Iterator {
    private int _leftToYield;
    private int[] _pi;

    /** Construct a permutation iterator over all permutations of n objects. */
    public PermIter(int n_) {
    _leftToYield = Util.fact(n_);
    _pi = new int[n_];
    }

    public boolean hasNext() { return _leftToYield > 0; }
    public Object next() {
    if (!hasNext()) throw new NoSuchElementException();
    unrank(_leftToYield--, _pi);
    return _pi;
    }

    public void remove() throws UnsupportedOperationException
    { throw new UnsupportedOperationException("PermIter.remove()"); }

    /**
     * Place into the array pi_ a permutation of integers
     * 0..pi_.length-1, of the given rank.
     * @param r_ (input) rank (number) of the permutation we want;
     *           must be between 0 and factorial(pi_.length)-1.
     * @param pi_ (output) array into which the r_'th permutaiton is to be
     *            placed.
     */
    public static void unrank(int r_, int[] pi_) {
    for (int i=0; i<pi_.length; i++)
        pi_[i] = i;
    _unrank_helper(pi_.length, r_, pi_);
    }

    /**
     * Generate a random permutation of n numbers, chosen uniformly
     * at random from all n! permutations.  Place it into indices of the
     * array pi at locations from_, from_+1, ..., to_-1.
     */
    public static void randomPermutation(int[] pi_, int from_, int to_, Random rand_) {
    int n = to_-from_;
    for (int i=0; i<n; i++)
        pi_[from_+i] = i;
    for (int i=n-1; i>=0; i--)
        _swap(pi_, from_+i, from_+rand_.nextInt(n));
    }

    /**
     * Generate a random permutation of n numbers, chosen uniformly
     * at random from all n! permutations.  Place it into indices of the
     * array pi.
     */
    public static void randomPermutation(int[] pi_, Random rand_) {
    randomPermutation(pi_, 0, pi_.length, rand_);
    }


    private static void _unrank_helper(int n_, int r_, int[] pi_) {
    if (n_ > 0) {
        _swap(pi_, n_-1, r_ % n_);
        _unrank_helper(n_-1, (int)Math.floor(r_ / n_), pi_);
    }
    }

    private static void _swap(int[] pi_, int i_, int j_) {
    int tmp = pi_[i_];
    pi_[i_] = pi_[j_];
    pi_[j_] = tmp;
    }

    /**
     * Place into the array pi_ a permutation of integers
     * 0..pi_.length-1, of the given rank.
     * @param r_ (input) rank (number) of the permutation we want;
     *           must be between 0 and factorial(pi_.length)-1.
     * @param pi_ (output) array into which the r_'th permutaiton is to be
     *            placed.
     */
    public static void unrank(BigInteger r_, int[] pi_) {
    for (int i=0; i<pi_.length; i++)
        pi_[i] = i;
    _unrank_helper(pi_.length, r_, pi_);
    }

    private static void _unrank_helper(int n_, BigInteger r_, int[] pi_) {
    if (n_ > 0) {
        BigInteger[] divRem = r_.divideAndRemainder(BigInteger.valueOf(n_));
        _swap(pi_, n_-1, divRem[1].intValue());
        _unrank_helper(n_-1, divRem[0], pi_);
    }
    }

    public static void main(String[] args_) {
    int[] pi = new int[10];
    Random r = new Random();
    for (int i=0; i<25; i++) {
        randomPermutation(pi, r);
        //System.out.println(Util.str(pi));
    }

    }
}


